#include<iostream>
#include<algorithm>

using namespace std;

const int N=510,INF=1e9+7;

int g[N][N],dist[N];
bool st[N];
int n,m;


int dijkstra()
{
	fill(dist,dist+N,INF);
	dist[1]=0;
	
	for(int i=1;i<=n;i++){
		int t=-1;
		for(int j=1;j<=n;j++){
			if(!st[j]&&(t==-1||dist[t]>dist[j])){
				t=j;
			}
		}
		st[t]=true;
		for(int j=1;j<=n;j++){
			dist[j]=min(dist[j],dist[t]+g[t][j]);
		}
	}
	
	if(dist[n]==INF) return -1;
	return dist[n];
}


int main()
{
	cin>>n>>m;
	fill(g[0],g[0]+N*N,INF);
	
	while(m--){
		int a,b,c;
		cin>>a>>b>>c;
		g[a][b]=min(g[a][b],c); 
	}
	
	cout<<dijkstra()<<endl;
	
	return 0;
} 
